/*************************************************************************
	> File Name: nqueens.cpp
	> Author: 
	> Mail: 
	> Created Time: 四 11/ 5 10:43:57 2015
 ************************************************************************/

#include<iostream>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;

//k代表第k个皇后, arr代表皇后放置的位置
//例如arr[1]代表第1个皇后的位置
bool place(int k, int *arr) {
    int i = 1;
    while (i < k) {
        if (arr[k] != arr[i] && abs(arr[k] - arr[i]) != k - i) {
            ++i;
        }
        else {
            return false;
        }
    }
    return true;
}

void nque(int n, int *arr, vector<vector<int> > &solution) {
    int k = 1;
    while (k > 0) {
        arr[k] = arr[k] + 1;
        while (arr[k] <= n && !place(k, arr)) {
            arr[k] = arr[k] + 1;
        }
        if (arr[k] <= n) {
            if (k == n) {
                vector<int> p;
                for (int i = 1; i <= n; ++i) {
                    cout << "the " << i << " queen position is:" << arr[i] << endl;
                    p.push_back(arr[i]);
                }
                cout << endl;
                solution.push_back(p);
            }
            else {
                k = k + 1;
                arr[k] = 0;     //下一个皇后从1位置开始放
            }
        }
        //backtrace
        else {
            k = k - 1;
        }
    }
}
void nque_recursion(int k, int *arr, int n, vector<vector<int> > &solution) {
    if (k > n) {
        vector<int> p;
        for (int i = 1; i <= n; ++i) {
            p.push_back(arr[i]);
        }
        solution.push_back(p);
        return;
    }

    for (int i = 1; i <= n; ++i) {
        arr[k] = i;
        if (place(k, arr)) {
            nque_recursion(k + 1, arr, n, solution);
        }
    }
}
int main(void) {
    int n;
    cout << "please input the number of queens : ";
    cin >> n;
    int arr[n + 1];
    vector<vector<int> > m;
    //int **solution = new int*[n + 1];
    for (int i = 0; i <= n; ++i)
        cout << arr[i] << " ";
    cout << endl;
    bzero(arr, sizeof(arr));

    for (int i = 0; i <= n; ++i)
        cout << arr[i] << " ";
    cout << endl;
    //nque(n, arr, m);
    nque_recursion(1, arr, n, m);
    for (auto i = m.begin(); i != m.end(); ++i) {
        for (auto j = (*i).begin(); j != (*i).end(); ++j) {
            cout << *j << " ";
        }
        cout << endl;
    }
    cout << "total solution : " << m.size() << endl;
    return 0;
}
